package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/4/20 20:54
 */
public class 岛屿数量 {

    public int numIslands(char[][] grid) {
        int m = grid.length;
        if(m == 0){
            return 0;
        }
        int n = grid[0].length;
        int count = 0;
        boolean[][] marked = new boolean[m][n];
        int[][] k = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!marked[i][j] && grid[i][j] == '1') {
                    count++;
                    dfs(i,j,grid,k,marked);
                }
            }
        }
        return count;
    }

    private void dfs(int i,int j,char[][] grid,int[][] k,boolean[][] marked){
        marked[i][j] = true;
        for(int l=0;l<4;l++){
            int x = i+k[l][0];
            int y = j+k[l][1];
            if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&grid[x][y]=='1'&&!marked[x][y]){
                dfs(x,y,grid,k,marked);
            }
        }
    }
}
